# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        # 计算每一个位置是第几小，判断左右
        def count(node):
            if not node:
                return 0
            return count(node.left) + count(node.right) + 1
        num_root = count(root.left)
        if num_root == k -1:
            return root.val
        elif num_root > k-1:
            return self.kthSmallest(root.left, k)
        else:
            return self.kthSmallest(root.right, k-num_root-1)




# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        self.k = k
        self.res = 0
        self.find_kth(root)
        return self.res
    def find_kth(self, root):

        # if not root.left:
        #     if self.k == 1:
        #         return root.val
        #     else:
        #         self.k -= 1
        #         return None
        if root.left:
           self.find_kth(root.left)
        self.k -= 1
        if self.k == 0:
            self.res = root.val
            return
        if root.right:
            self.find_kth(root.right)




